package leetcode.code1579;

import java.util.Arrays;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution2 implements IDebug {
	int[] a;
	int[] b;
	int[] s;

	public int maxNumEdgesToRemove(int n, int[][] edges) {
		a = new int[n];
		b = new int[n];
		s = new int[] { n, n };
		for (int i = 0; i < n; i++) {
			a[i] = i;
			b[i] = i;
		}
		int ans = edges.length;
		for (int edge[] : edges) {
			int ti = edge[0], ui = edge[1] - 1, vi = edge[2] - 1;
			if (ti == 3 && !same(ui, vi, a)) {
				ans -= 1;
				union(ui, vi, a, 0);
				union(ui, vi, b, 1);
			}
		}
		for (int edge[] : edges) {
			int ti = edge[0], ui = edge[1] - 1, vi = edge[2] - 1;
			if (ti == 1 && !same(ui, vi, a)) {
				union(ui, vi, a, 0);
				ans -= 1;
			} else if (ti == 2 && !same(ui, vi, b)) {
				union(ui, vi, b, 1);
				ans -= 1;
			}
		}
		return s[0] == s[1] && s[1] == 1 ? ans : -1;
	}

	private void union(int ui, int vi, int[] arr, int type) {
		int pui = find(ui, arr), pvi = find(vi, arr);
		if (pui != pvi) {
			arr[pvi] = pui;
			s[type]--;
		}
	}

	private boolean same(int ui, int vi, int[] arr) {
		return find(ui, arr) == find(vi, arr);
	}

	private int find(int i, int[] arr) {
		if (arr[i] != i) {
			arr[i] = find(arr[i], arr);
		}
		return arr[i];
	}

	@Override
	public void debug4() {
		H.compare(2, this.maxNumEdgesToRemove(4, H.str2array1("[[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
